#我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

# 1 target <= 0 大矩形为<= 2*0,直接return 1；
# 2 target = 1大矩形为2*1，只有一种摆放方法，return1；
# 3️target = 2 大矩形为2*2，有两种摆放方法，return2；
# 4️target = n 分为两步考虑：
#  第一次摆放一块 2*1 的小矩阵，则摆放方法总共为f(target - 1)
# 第一次摆放一块1*2的小矩阵，则摆放方法总共为f(target-2)
# 因为，摆放了一块1*2的小矩阵（用√√表示），对应下方的1*2（用××表示）摆放方法就确定了，所以为f(targte-2)

def cover_rect(n):
    if n<=1:
        return 1
    elif n==2:
        return 2
    else:
        return (cover_rect(n-1)+cover_rect(n-2))


# print(cover_rect(5))
# 这就变成了斐波那契数列，但是上面的做法没有记录重复的结论，所以通不过的，改进一下：
s= [_ for _ in range(0,100)]
def cover_rect1(n):
    if n==0:
        return 0
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        s[n]=(cover_rect1(n-1)+cover_rect1(n-2))
        return s[n]

# print(cover_rect1(15))

# 遗憾的是，牛博网上的服务器连这个递归也不行，只好用循环

def cover_rect2(n):
    if n==0:
        return 0
    if n==1:
        return 1
    elif n==2:
        return 2
    else:
        s = []*n
        s.append(1)
        s.append(2)
        for i in range(2,n):
            s.append(s[i-1]+s[i-2])
        return s[n-1]

print(cover_rect2(15))